/*
题目: 最大人工岛
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

https://leetcode.cn/problems/making-a-large-island
 */
public class LargestIsland {
    int row, col ;
    int[][] status ; // 状态

    int[] dir = new int[] {0, -1, 0, 1, 0}; // 方向
    Map<Integer, Integer> island = new HashMap<> (); // 岛屿的编号 和 对应的面积
    int mark = 1; // 岛屿的编号
    public int largestIsland(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        status = new int[row][col]; // 记录每一个岛屿的状态, 0 表示河, 非 0 表示 所属 的陆地
        boolean[][] visited = new boolean[row][col]; // 标记是否访问过

        List<int[]> spaces = new ArrayList<>(); // 记录空白位置
        int src = 1;
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; j ++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    int area = DFS(grid, visited, i , j);  // 获取一整个岛屿的面积
                    src = Math.max(src, area);  // 顺便更新一下, 防止都是 孤岛
                    island.put(mark ++, area); // 将 岛屿编号, 并 映射 面积
                } else if (grid[i][j] == 0) {  // 是河流
                    spaces.add(new int[] {i, j});
                }
            }
        }

        if (spaces.isEmpty() || spaces.size() == row * col) return src; // 如果没有空白处, 或者都是空白处 直接返回
        // 遍历所有空白处
        for (int[] space : spaces) {
            int x = space[0], y = space[1]; // 坐标

            Set<Integer> set = new HashSet<> (); // 对岛的编号去重
            for (int i = 0; i < 4; i ++) {
                int nextX = x + dir[i];
                int nextY = y + dir[i + 1];

                if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
                    continue ;
                }
                set.add(status[nextX][nextY]);
            }

            int tmp = 0; // 临时面积
            for (Integer i : set) {
                if (i != 0) tmp += island.get(i); // 如果周围不是 河流, 就都串起来
            }
            src = Math.max(src, tmp + 1);
        }

        return src;
    }

    private int DFS(int[][] grid, boolean[][] visited, int x, int y) {
        if (grid[x][y] == 0) return 0;

        visited[x][y] = true;
        status[x][y] = mark; // 标记 岛 号
        int ret = 1;
        for (int i = 0; i < 4; i ++) {
            int nextX = x + dir[i];
            int nextY = y + dir[i + 1];

            // 越界或者已经访问过
            if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col || visited[nextX][nextY]) {
                continue ;
            }

            ret += DFS(grid, visited, nextX, nextY);
        }
        return ret;
    }
}
